﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include <math.h>
// 原题连接：https://leetcode.cn/problems/palindrome-number
// 题目描述：
/*
给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
例如，121 是回文，而 123 不是。
 
示例 1：
输入：x = 121
输出：true

示例 2：
输入：x = -121
输出：false
解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

示例 3：
输入：x = 10
输出：false
解释：从右向左读, 为 01 。因此它不是一个回文数。
*/

// 方法1——数字转化成字符串
/*
思路：
我们可以先把数字转化为字符串，再将得到的字符串逆序
对比逆序前和逆序后的字符串是否相等，相等则返回true，
不相等则返回false
*/
// 有了以上思路，那我们写起代码来也就水到渠成了：
bool isPalindrome1(int x) {
	// 如果x为负数则直接返回false
	if (x < 0) {
		return false;
	}
	char num[11] = { 0 }; // 整型最长有十位
	// 先将数字转化成字符串
	int n = 0; // 记录该数字有多少位，也即转化成的字符串的长度
	while (x) {
		num[n] = (x % 10) + '0';
		n++;
		x /= 10;
	}
	// 此时得到的num的内容已经是逆序了的
	num[n] = '\0'; // 在末尾加上字符串结束标志
	char temp[11] = { 0 };
	strcpy(temp, num); // 将num拷贝到temp中
	// 再将temp逆序
	int left = 0;
	int right = n - 1;
	while (left < right) {
		char tmp = temp[left];
		temp[left] = temp[right];
		temp[right] = tmp;
		left++;
		right--;
	}
	// 比较逆序后的temp和num
	if (strcmp(num, temp) == 0) {
		return true;
}
	return false;
}
// 时间复杂度：O(n),n为数字的位数或字符串的长度，转化时的复杂度为log10n,逆序时的复杂度为n/2故复杂度为O(n)。
// 空间复杂度：O(n),我们需要用到与数组长度相等的额外空间。

// 优化
// 其实我们并不用再将转化后的字符串逆序，我们可以直接在原字符串上判断，只要判断它左右两边是否全都相等即可
bool isPalindrome2(int x) {
	// 如果x为负数则直接返回false
	if (x < 0) {
		return false;
	}
	char num[11] = { 0 }; // 整型最长有十位
	// 先将数字转化成字符串
	int n = 0; // 记录该数字有多少位，也即转化成的字符串的长度
	while (x) {
		num[n] = (x % 10) + '0';
		n++;
		x /= 10;
	}
	num[n] = '\0'; // 在末尾加上字符串结束标志
	// 此时得到的num的内容已经是逆序了的
	int left = 0;
	int right = n - 1;
	// 对比num的左右两边是否全都相等
	while (left < right) {
		if (num[left] == num[right]) {
			left++;
			right--;
		}
		else {
			return false;
		}
	}
	return true;
}
// 时间复杂度：O(n),n为数字的位数或字符串的长度，转化时的复杂度为log10n,比较时的复杂度为n/2故复杂度为O(n)。
// 空间复杂度：O(n),我们需要用到与数组长度相等的额外空间。

// 方法2——反转数字的一半
/*
和上一题的改进思路差不多，我们可以只把数字的一半进行反转(例如后一半)
用一个变量reverse_number来保存，每取到一位数字我们就让x / 10,
故随着循环的不断进行，x将越来越小，reverse_number将越来越大，
对于偶数位的数字，如果出现x == reverse_number则循环可以停止，表示x是一个回文数
对于奇数，如果出现x == reverse_number / 10或x / 10 == reverse_number则循环可以停止，表示x是一个回文数
*/

// 有了以上思路，那我们写起代码来也就水到渠成了：
bool isPalindrome2(int x) {
	// 如果x为负数或者末尾有0，直接返回false
	if (x < 0 || (x % 10 == 0 && x != 0)) {
		return false;
	}
	int reverse_number = 0;
	while (x > reverse_number) {
		reverse_number = reverse_number * 10 + (x % 10);
		x /= 10;
	}
	return x == reverse_number || x == reverse_number / 10;
}
// 时间复杂度：O(log10(N)),N为数字x的值，每取一个数字，我们都要对x进行除10操作，所以时间复杂度为O(log10(N))。
// 空间复杂度：O(1)，我们只需要一个int类型变量reverse_number来帮我们存储反转后的数字。

// 方法3——数学解法
/*
思路：思路和方法1的改进版的思路差不多，只不过我们这次是直接
取出x两端的数字进行比较(即取出最高位和最低位)。不再次转化成字符串。
取出x的最高位可以用x / "最高位权重"来获取，取得最低位可以用x % 10来获取
取完一轮后就要去除x的最高位和最低位，去除最高位可以用x %= "最高位权重"达到
而去除最低位则要用x /= 10 来完成;
*/


// 有了以上思路，那我们写起代码来也就水到渠成了：
bool isPalindrome3(int x) {
	if (x < 0) {
		return false;
	}
	// 首先获得x有多少位
	int temp = x;
	int n = 0; // 标记x有多少位
	while (temp) {
		n++;
		temp /= 10;
	}
	int high = 0; // 保存x的高位
	int low = 0; // 保存x的低位
	int weight = pow(10, n - 1); // 保存x的高权重
	while (x > 0) {
		high = x / weight;
		low = x % 10;
		if (high != low) {
			return false;
		}
		x = (x % weight) / 10;
		weight /= 100; // 减少了两位
	}
	return true;
}
// 时间复杂度：O(n)，n为x的位数。
// 空间复杂度：O(1)



